package 中等.搜索.广度优先搜索;

import util.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中
 * 的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
 * 每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-width-of-binary-tree
 */
public class 二叉树最大宽度_662 {

    public static void main(String[] args) {

    }

    /**
     * 给每个节点加个索引
     * .            1
     * .         2    3
     * .       4  5  6  7
     * 索引的计算 当前节点的索引为 curIdx ，那么
     * 右子节点 rightIdx = 2 * curIdx + 1
     * 左子节点 leftIdx = 2 * curIdx
     * 宽度等于当前层最右边的索引 - 最左边的索引 +1
     *
     * @param root
     * @return
     */
    public int widthOfBinaryTree(TreeNode root) {
        int count = 0;
        Deque<TreeNode> queue = new ArrayDeque<>();
        root.val = 1;
        queue.addLast(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            count = Math.max(count, queue.peekLast().val - queue.peekFirst().val + 1);
            while (size-- > 0) {
                TreeNode curNode = queue.pollFirst();
                if (curNode.left != null) {
                    curNode.left.val = curNode.val * 2;
                    queue.addLast(curNode.left);
                }
                if (curNode.right != null) {
                    curNode.right.val = curNode.val * 2 + 1;
                    queue.addLast(curNode.right);
                }
            }
        }
        return count;
    }

}
